package demo1;

public class LinkList826 implements IList{
    class LinkNode{
        int val;
        LinkNode next;
        public LinkNode(int val){
            this.val=val;
        }
    }
    LinkNode head;
    public void create(){
        LinkNode node1=new LinkNode(1);
        LinkNode node2=new LinkNode(3);
        LinkNode node3=new LinkNode(2);
        LinkNode node4=new LinkNode(2);
        LinkNode node5=new LinkNode(5);
        LinkNode node6=new LinkNode(2);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        node5.next=node6;
        head=node1;

    }
    public int size() {
        LinkNode cur=head;
        int size=0;
        while(cur!=null){
            cur=cur.next;
            size++;
        }
        return size;
    }
    @Override
    public void addFirst(int date) {
     LinkNode node=new LinkNode(date);
        node.next=head;
        head=node;

    }

    @Override
    public void addLast(int date) {
        LinkNode node=new LinkNode(date);
        if(head==null){
            head=node;
            return;
        }
        LinkNode cur=head;
        while(cur.next!=null){
            cur=cur.next;
        }
        cur.next=node;
    }

    @Override
    public void addIndex(int index, int date) {
        try {
            if(index<0||index>size()){
                System.out.println("输入下标不合法！！！");
            throw new RuntimeException();
            }
            LinkNode node=new LinkNode(date);
            if(index==0){
                addFirst(date);
                return;
            }
            if(index==size()){
                addLast(date);
                return;
            }
            LinkNode cur=findNode(index);
            node.next=cur.next;
            cur.next=node;

        }catch (RuntimeException e){
            System.out.println("输入下标不合法！！！");
        }

    }
    private LinkNode findNode(int index){
        LinkNode cur=head;
        while(index-1!=0){
            cur=cur.next;
            index--;
        }
        return cur;
    }

    @Override
    public int findIndex(int index) {
        try{
            if(index<0||index>size()){
                throw new RuntimeException();
            }
            LinkNode cur=findNode(index);
            return cur.next.val;
        }catch (RuntimeException e){
            System.out.println("下标不合法的！！！");
        }
        return -1;
    }

    @Override
    public boolean contain(int date) {
        LinkNode cur=head;
        while (cur!=null){
            if(cur.val==date){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }

    @Override
    public void move(int date) {
        if(head==null){
            return;
        }
        if(head.val==date){
            head=head.next;
            return;
        }
        LinkNode cur=findNodekey(date);
        if(cur==null){
            return;
        }
        LinkNode del=cur.next;
        cur.next=del.next;
        }
        private LinkNode findNodekey(int date){
        LinkNode cur=head;
        while(cur.next!=null){
            if(cur.next.val==date){
                return cur;
            }
            cur=cur.next;
        }
        return null;
        }

    @Override
    public void moveAll(int date) {
        LinkNode prev=head;
        LinkNode cur=head.next;
        while (cur!=null){
            if(cur.val==date){
                prev.next=cur.next;
                cur=cur.next;
            }else{
                prev=cur;
                cur=cur.next;
            }
        }
        if(head.val==date){
            head=head.next;
        }

    }

    @Override
    public void display() {
    LinkNode cur=head;
    while (cur!=null){
        System.out.print(cur.val+" ");
        cur=cur.next;
    }
    }

    @Override
    public void clear() {
        head=null;
    }
    //求链表的中间节点
    public int findNode(LinkList826 list1){
        if(list1.head==null){
            System.out.println("链表为空！！！");
        }
        LinkNode fast=list1.head;
        LinkNode slow=list1.head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow.val;
    }
    //求链表的倒数第k个节点
    public int findK(LinkList826 list,int k){
        LinkNode fast=list.head;
        LinkNode slow=list.head;
        if(list.head==null){
            return -1;
        }
        if(k<=0||k>list.size()){
            return -1;
        }
        int count=0;
        while (count!=k-1){
            fast=fast.next;
            count++;
            if(fast==null){
                return -1;
            }
        }
        while (fast.next!=null){
            slow=slow.next;
            fast=fast.next;
        }
        return slow.val;
    }
    //合并两个链表
    public void mergeTwo(LinkList826 list1,LinkList826 list2){
        LinkNode node0=new LinkNode(1);
        LinkNode tmp=node0;
        while (list1.head!=null&&list2.head!=null){
            if(list1.head.val<list2.head.val){
                tmp.next=list1.head;
                list1.head=list1.head.next;
                tmp=tmp.next;
            }else {
                tmp.next=list2.head;
                list2.head=list2.head.next;
                tmp=tmp.next;
            }
        }
        if(list1.head!=null){
            tmp.next=list1.head;
        }
        if(list2.head!=null){
            tmp.next=list2.head;
        }
        display2(node0.next);
    }
    private void display2(LinkNode head){
        LinkNode cur=head;
        System.out.println("合并后的链表为：");
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
    }

}
